#pragma warning disable IDE0073 // The file header does not match the required text
//----------------------------------------------------------------
// Copyright (c) Microsoft Corporation.  All rights reserved.
//----------------------------------------------------------------

namespace System;

using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Collections.Specialized;
using System.Globalization;
using System.Runtime;
using System.Runtime.CompilerServices;
using System.ServiceModel;
using System.Text;
using System.Threading;

[TypeForwardedFrom("System.ServiceModel.Web, Version=3.5.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35")]
public class UriTemplate {
	internal readonly int firstOptionalSegment;

	internal readonly string originalTemplate;
	internal readonly Dictionary<string, UriTemplateQueryValue> queries; // keys are original case specified in UriTemplate constructor, dictionary ignores case
	internal readonly List<UriTemplatePathSegment> segments;
	internal const string WildcardPath = "*";
	readonly Dictionary<string, string> additionalDefaults; // keys are original case specified in UriTemplate constructor, dictionary ignores case
	readonly string fragment;

	readonly bool ignoreTrailingSlash;

	const string NullableDefault = "null";
	readonly WildcardInfo wildcard;
	IDictionary<string, string> defaults;
	ConcurrentDictionary<string, string> unescapedDefaults;

	VariablesCollection variables;

	// constructors validates that template is well-formed
	public UriTemplate(string template)
		: this(template, false) {
	}
	public UriTemplate(string template, bool ignoreTrailingSlash)
		: this(template, ignoreTrailingSlash, null) {
	}
	public UriTemplate(string template, IDictionary<string, string> additionalDefaults)
		: this(template, false, additionalDefaults) {
	}
	public UriTemplate(string template, bool ignoreTrailingSlash, IDictionary<string, string> additionalDefaults) {
		if (template == null) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("template");
		}
		this.originalTemplate = template;
		this.ignoreTrailingSlash = ignoreTrailingSlash;
		this.segments = new List<UriTemplatePathSegment>();
		this.queries = new Dictionary<string, UriTemplateQueryValue>(StringComparer.OrdinalIgnoreCase);

		// parse it
		string pathTemplate;
		string queryTemplate;
		// ignore a leading slash
		if (template.StartsWith("/", StringComparison.Ordinal)) {
			template = template.Substring(1);
		}
		// pull out fragment
		int fragmentStart = template.IndexOf('#');
		if (fragmentStart == -1) {
			this.fragment = "";
		} else {
			this.fragment = template.Substring(fragmentStart + 1);
			template = template.Substring(0, fragmentStart);
		}
		// pull out path and query
		int queryStart = template.IndexOf('?');
		if (queryStart == -1) {
			queryTemplate = string.Empty;
			pathTemplate = template;
		} else {
			queryTemplate = template.Substring(queryStart + 1);
			pathTemplate = template.Substring(0, queryStart);
		}
		template = null; // to ensure we don't accidentally reference this variable any more

		// setup path template and validate
		if (!string.IsNullOrEmpty(pathTemplate)) {
			int startIndex = 0;
			while (startIndex < pathTemplate.Length) {
				// Identify the next segment
				int endIndex = pathTemplate.IndexOf('/', startIndex);
				string segment;
				if (endIndex != -1) {
					segment = pathTemplate.Substring(startIndex, endIndex + 1 - startIndex);
					startIndex = endIndex + 1;
				} else {
					segment = pathTemplate.Substring(startIndex);
					startIndex = pathTemplate.Length;
				}
				// Checking for wildcard segment ("*") or ("{*<var name>}")
				UriTemplatePartType wildcardType;
				if ((startIndex == pathTemplate.Length) &&
					UriTemplateHelpers.IsWildcardSegment(segment, out wildcardType)) {
					switch (wildcardType) {
						case UriTemplatePartType.Literal:
							this.wildcard = new WildcardInfo(this);
							break;

						case UriTemplatePartType.Variable:
							this.wildcard = new WildcardInfo(this, segment);
							break;

						default:
							Fx.Assert("Error in identifying the type of the wildcard segment");
							break;
					}
				} else {
					this.segments.Add(UriTemplatePathSegment.CreateFromUriTemplate(segment, this));
				}
			}
		}

		// setup query template and validate
		if (!string.IsNullOrEmpty(queryTemplate)) {
			int startIndex = 0;
			while (startIndex < queryTemplate.Length) {
				// Identify the next query part
				int endIndex = queryTemplate.IndexOf('&', startIndex);
				int queryPartStart = startIndex;
				int queryPartEnd;
				if (endIndex != -1) {
					queryPartEnd = endIndex;
					startIndex = endIndex + 1;
					if (startIndex >= queryTemplate.Length) {
						throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(
							SR.UTQueryCannotEndInAmpersand, this.originalTemplate)));
					}
				} else {
					queryPartEnd = queryTemplate.Length;
					startIndex = queryTemplate.Length;
				}
				// Checking query part type; identifying key and value
				int equalSignIndex = queryTemplate.IndexOf('=', queryPartStart, queryPartEnd - queryPartStart);
				string key;
				string value;
				if (equalSignIndex >= 0) {
					key = queryTemplate.Substring(queryPartStart, equalSignIndex - queryPartStart);
					value = queryTemplate.Substring(equalSignIndex + 1, queryPartEnd - equalSignIndex - 1);
				} else {
					key = queryTemplate.Substring(queryPartStart, queryPartEnd - queryPartStart);
					value = null;
				}
				if (string.IsNullOrEmpty(key)) {
					throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(
						SR.UTQueryCannotHaveEmptyName, this.originalTemplate)));
				}
				if (UriTemplateHelpers.IdentifyPartType(key) != UriTemplatePartType.Literal) {
					throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("template", SR.GetString(
						SR.UTQueryMustHaveLiteralNames, this.originalTemplate));
				}
				// Adding a new entry to the queries dictionary
				key = UrlUtility.UrlDecode(key, Encoding.UTF8);
				if (this.queries.ContainsKey(key)) {
					throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(
						SR.UTQueryNamesMustBeUnique, this.originalTemplate)));
				}
				this.queries.Add(key, UriTemplateQueryValue.CreateFromUriTemplate(value, this));
			}
		}

		// Process additional defaults (if has some) :
		if (additionalDefaults != null) {
			if (this.variables == null) {
				if (additionalDefaults.Count > 0) {
					this.additionalDefaults = new Dictionary<string, string>(additionalDefaults, StringComparer.OrdinalIgnoreCase);
				}
			} else {
				foreach (KeyValuePair<string, string> kvp in additionalDefaults) {
					string uppercaseKey = kvp.Key.ToUpperInvariant();
					if ((this.variables.DefaultValues != null) && this.variables.DefaultValues.ContainsKey(uppercaseKey)) {
						throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("additionalDefaults",
							SR.GetString(SR.UTAdditionalDefaultIsInvalid, kvp.Key, this.originalTemplate));
					}
					if (this.variables.PathSegmentVariableNames.Contains(uppercaseKey)) {
						this.variables.AddDefaultValue(uppercaseKey, kvp.Value);
					} else if (this.variables.QueryValueVariableNames.Contains(uppercaseKey)) {
						throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
							SR.GetString(SR.UTDefaultValueToQueryVarFromAdditionalDefaults, this.originalTemplate,
							uppercaseKey)));
					} else if (string.Compare(kvp.Value, UriTemplate.NullableDefault, StringComparison.OrdinalIgnoreCase) == 0) {
						throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
							SR.GetString(SR.UTNullableDefaultAtAdditionalDefaults, this.originalTemplate,
							uppercaseKey)));
					} else {
						if (this.additionalDefaults == null) {
							this.additionalDefaults = new Dictionary<string, string>(additionalDefaults.Count, StringComparer.OrdinalIgnoreCase);
						}
						this.additionalDefaults.Add(kvp.Key, kvp.Value);
					}
				}
			}
		}

		// Validate defaults (if should)
		if ((this.variables != null) && (this.variables.DefaultValues != null)) {
			this.variables.ValidateDefaults(out this.firstOptionalSegment);
		} else {
			this.firstOptionalSegment = this.segments.Count;
		}
	}

	public IDictionary<string, string> Defaults {
		get {
			if (this.defaults == null) {
				Interlocked.CompareExchange<IDictionary<string, string>>(ref this.defaults, new UriTemplateDefaults(this), null);
			}
			return this.defaults;
		}
	}
	public bool IgnoreTrailingSlash {
		get {
			return this.ignoreTrailingSlash;
		}
	}
	public ReadOnlyCollection<string> PathSegmentVariableNames {
		get {
			if (this.variables == null) {
				return VariablesCollection.EmptyCollection;
			} else {
				return this.variables.PathSegmentVariableNames;
			}
		}
	}
	public ReadOnlyCollection<string> QueryValueVariableNames {
		get {
			if (this.variables == null) {
				return VariablesCollection.EmptyCollection;
			} else {
				return this.variables.QueryValueVariableNames;
			}
		}
	}

	internal bool HasNoVariables {
		get {
			return (this.variables == null);
		}
	}
	internal bool HasWildcard {
		get {
			return (this.wildcard != null);
		}
	}

	// make a Uri by subbing in the values, throw on bad input
	public Uri BindByName(Uri baseAddress, IDictionary<string, string> parameters) {
		return BindByName(baseAddress, parameters, false);
	}
	public Uri BindByName(Uri baseAddress, IDictionary<string, string> parameters, bool omitDefaults) {
		if (baseAddress == null) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("baseAddress");
		}
		if (!baseAddress.IsAbsoluteUri) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("baseAddress", SR.GetString(
				SR.UTBadBaseAddress));
		}

		BindInformation bindInfo;
		if (this.variables == null) {
			bindInfo = PrepareBindInformation(parameters, omitDefaults);
		} else {
			bindInfo = this.variables.PrepareBindInformation(parameters, omitDefaults);
		}
		return Bind(baseAddress, bindInfo, omitDefaults);
	}
	public Uri BindByName(Uri baseAddress, NameValueCollection parameters) {
		return BindByName(baseAddress, parameters, false);
	}
	public Uri BindByName(Uri baseAddress, NameValueCollection parameters, bool omitDefaults) {
		if (baseAddress == null) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("baseAddress");
		}
		if (!baseAddress.IsAbsoluteUri) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("baseAddress", SR.GetString(
				SR.UTBadBaseAddress));
		}

		BindInformation bindInfo;
		if (this.variables == null) {
			bindInfo = PrepareBindInformation(parameters, omitDefaults);
		} else {
			bindInfo = this.variables.PrepareBindInformation(parameters, omitDefaults);
		}
		return Bind(baseAddress, bindInfo, omitDefaults);
	}
	public Uri BindByPosition(Uri baseAddress, params string[] values) {
		if (baseAddress == null) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("baseAddress");
		}
		if (!baseAddress.IsAbsoluteUri) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("baseAddress", SR.GetString(
				SR.UTBadBaseAddress));
		}

		BindInformation bindInfo;
		if (this.variables == null) {
			if (values.Length > 0) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new FormatException(SR.GetString(
					SR.UTBindByPositionNoVariables, this.originalTemplate, values.Length)));
			}
			bindInfo = new BindInformation(this.additionalDefaults);
		} else {
			bindInfo = this.variables.PrepareBindInformation(values);
		}
		return Bind(baseAddress, bindInfo, false);
	}

	// A note about UriTemplate equivalency:
	//  The introduction of defaults and, more over, terminal defaults, broke the simple
	//  intuative notion of equivalency between templates. We will define equivalent
	//  templates as such based on the structure of them and not based on the set of uri
	//  that are matched by them. The result is that, even though they do not match the
	//  same set of uri's, the following templates are equivalent:
	//      - "/foo/{bar}"
	//      - "/foo/{bar=xyz}"
	//  A direct result from the support for 'terminal defaults' is that the IsPathEquivalentTo
	//  method, which was used both to determine the equivalence between templates, as 
	//  well as verify that all the templates, combined together in the same PathEquivalentSet, 
	//  are equivalent in thier path is no longer valid for both purposes. We will break 
	//  it to two distinct methods, each will be called in a different case.
	public bool IsEquivalentTo(UriTemplate other) {
		if (other == null) {
			return false;
		}
		if (other.segments == null || other.queries == null) {
			// they never are null, but PreSharp is complaining, 
			// and warning suppression isn't working
			return false;
		}
		if (!IsPathFullyEquivalent(other)) {
			return false;
		}
		if (!IsQueryEquivalent(other)) {
			return false;
		}
		Fx.Assert(UriTemplateEquivalenceComparer.Instance.GetHashCode(this) == UriTemplateEquivalenceComparer.Instance.GetHashCode(other), "bad GetHashCode impl");
		return true;
	}

	public UriTemplateMatch Match(Uri baseAddress, Uri candidate) {
		if (baseAddress == null) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("baseAddress");
		}
		if (!baseAddress.IsAbsoluteUri) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("baseAddress", SR.GetString(
				SR.UTBadBaseAddress));
		}
		if (candidate == null) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("candidate");
		}

		// ensure that the candidate is 'under' the base address
		if (!candidate.IsAbsoluteUri) {
			return null;
		}
		string basePath = UriTemplateHelpers.GetUriPath(baseAddress);
		string candidatePath = UriTemplateHelpers.GetUriPath(candidate);
		if (candidatePath.Length < basePath.Length) {
			return null;
		}
		if (!candidatePath.StartsWith(basePath, StringComparison.OrdinalIgnoreCase)) {
			return null;
		}

		// Identifying the relative segments \ checking matching to the path :
		int numSegmentsInBaseAddress = baseAddress.Segments.Length;
		string[] candidateSegments = candidate.Segments;
		int numMatchedSegments;
		Collection<string> relativeCandidateSegments;
		if (!IsCandidatePathMatch(numSegmentsInBaseAddress, candidateSegments,
			out numMatchedSegments, out relativeCandidateSegments)) {
			return null;
		}
		// Checking matching to the query (if should) :
		NameValueCollection candidateQuery = null;
		if (!UriTemplateHelpers.CanMatchQueryTrivially(this)) {
			candidateQuery = UriTemplateHelpers.ParseQueryString(candidate.Query);
			if (!UriTemplateHelpers.CanMatchQueryInterestingly(this, candidateQuery, false)) {
				return null;
			}
		}

		// We matched; lets build the UriTemplateMatch
		return CreateUriTemplateMatch(baseAddress, candidate, null, numMatchedSegments,
			relativeCandidateSegments, candidateQuery);
	}

	public override string ToString() {
		return this.originalTemplate;
	}

	internal string AddPathVariable(UriTemplatePartType sourceNature, string varDeclaration) {
		bool hasDefaultValue;
		return AddPathVariable(sourceNature, varDeclaration, out hasDefaultValue);
	}
	internal string AddPathVariable(UriTemplatePartType sourceNature, string varDeclaration,
		out bool hasDefaultValue) {
		if (this.variables == null) {
			this.variables = new VariablesCollection(this);
		}
		return this.variables.AddPathVariable(sourceNature, varDeclaration, out hasDefaultValue);
	}
	internal string AddQueryVariable(string varDeclaration) {
		if (this.variables == null) {
			this.variables = new VariablesCollection(this);
		}
		return this.variables.AddQueryVariable(varDeclaration);
	}

	internal UriTemplateMatch CreateUriTemplateMatch(Uri baseUri, Uri uri, object data,
		int numMatchedSegments, Collection<string> relativePathSegments, NameValueCollection uriQuery) {
		UriTemplateMatch result = new UriTemplateMatch();
		result.RequestUri = uri;
		result.BaseUri = baseUri;
		if (uriQuery != null) {
			result.SetQueryParameters(uriQuery);
		}
		result.SetRelativePathSegments(relativePathSegments);
		result.Data = data;
		result.Template = this;
		for (int i = 0; i < numMatchedSegments; i++) {
			this.segments[i].Lookup(result.RelativePathSegments[i], result.BoundVariables);
		}
		if (this.wildcard != null) {
			this.wildcard.Lookup(numMatchedSegments, result.RelativePathSegments,
				result.BoundVariables);
		} else if (numMatchedSegments < this.segments.Count) {
			BindTerminalDefaults(numMatchedSegments, result.BoundVariables);
		}
		if (this.queries.Count > 0) {
			foreach (KeyValuePair<string, UriTemplateQueryValue> kvp in this.queries) {
				kvp.Value.Lookup(result.QueryParameters[kvp.Key], result.BoundVariables);
				//UriTemplateHelpers.AssertCanonical(varName);
			}
		}
		if (this.additionalDefaults != null) {
			foreach (KeyValuePair<string, string> kvp in this.additionalDefaults) {
				result.BoundVariables.Add(kvp.Key, UnescapeDefaultValue(kvp.Value));
			}
		}
		Fx.Assert(result.RelativePathSegments.Count - numMatchedSegments >= 0, "bad segment computation");
		result.SetWildcardPathSegmentsStart(numMatchedSegments);

		return result;
	}

	internal bool IsPathPartiallyEquivalentAt(UriTemplate other, int segmentsCount) {
		// Refer to the note on template equivalency at IsEquivalentTo
		// This method checks if any uri with given number of segments, which can be matched
		//  by this template, can be also matched by the other template.
		Fx.Assert(segmentsCount >= this.firstOptionalSegment - 1, "How can that be? The Trie is constructed that way!");
		Fx.Assert(segmentsCount <= this.segments.Count, "How can that be? The Trie is constructed that way!");
		Fx.Assert(segmentsCount >= other.firstOptionalSegment - 1, "How can that be? The Trie is constructed that way!");
		Fx.Assert(segmentsCount <= other.segments.Count, "How can that be? The Trie is constructed that way!");
		for (int i = 0; i < segmentsCount; ++i) {
			if (!this.segments[i].IsEquivalentTo(other.segments[i],
				((i == segmentsCount - 1) && (this.ignoreTrailingSlash || other.ignoreTrailingSlash)))) {
				return false;
			}
		}
		return true;
	}
	internal bool IsQueryEquivalent(UriTemplate other) {
		if (this.queries.Count != other.queries.Count) {
			return false;
		}
		foreach (string key in this.queries.Keys) {
			UriTemplateQueryValue utqv = this.queries[key];
			UriTemplateQueryValue otherUtqv;
			if (!other.queries.TryGetValue(key, out otherUtqv)) {
				return false;
			}
			if (!utqv.IsEquivalentTo(otherUtqv)) {
				return false;
			}
		}
		return true;
	}

	internal static Uri RewriteUri(Uri uri, string host) {
		if (!string.IsNullOrEmpty(host)) {
			string originalHostHeader = uri.Host + ((!uri.IsDefaultPort) ? ":" + uri.Port.ToString(CultureInfo.InvariantCulture) : string.Empty);
			if (!String.Equals(originalHostHeader, host, StringComparison.OrdinalIgnoreCase)) {
				Uri sourceUri = new Uri(String.Format(CultureInfo.InvariantCulture, "{0}://{1}", uri.Scheme, host));
				return (new UriBuilder(uri) { Host = sourceUri.Host, Port = sourceUri.Port }).Uri;
			}
		}
		return uri;
	}

	Uri Bind(Uri baseAddress, BindInformation bindInfo, bool omitDefaults) {
		UriBuilder result = new UriBuilder(baseAddress);
		int parameterIndex = 0;
		int lastPathParameter = ((this.variables == null) ? -1 : this.variables.PathSegmentVariableNames.Count - 1);
		int lastPathParameterToBind;
		if (lastPathParameter == -1) {
			lastPathParameterToBind = -1;
		} else if (omitDefaults) {
			lastPathParameterToBind = bindInfo.LastNonDefaultPathParameter;
		} else {
			lastPathParameterToBind = bindInfo.LastNonNullablePathParameter;
		}
		string[] parameters = bindInfo.NormalizedParameters;
		IDictionary<string, string> extraQueryParameters = bindInfo.AdditionalParameters;
		// Binding the path :
		StringBuilder pathString = new StringBuilder(result.Path);
		if (pathString[pathString.Length - 1] != '/') {
			pathString.Append('/');
		}
		if (lastPathParameterToBind < lastPathParameter) {
			// Binding all the parameters we need
			int segmentIndex = 0;
			while (parameterIndex <= lastPathParameterToBind) {
				Fx.Assert(segmentIndex < this.segments.Count,
					"Calculation of LastNonDefaultPathParameter,lastPathParameter or parameterIndex failed");
				this.segments[segmentIndex++].Bind(parameters, ref parameterIndex, pathString);
			}
			Fx.Assert(parameterIndex == lastPathParameterToBind + 1,
				"That is the exit criteria from the loop");
			// Maybe we have some literals yet to bind
			Fx.Assert(segmentIndex < this.segments.Count,
				"Calculation of LastNonDefaultPathParameter,lastPathParameter or parameterIndex failed");
			while (this.segments[segmentIndex].Nature == UriTemplatePartType.Literal) {
				this.segments[segmentIndex++].Bind(parameters, ref parameterIndex, pathString);
				Fx.Assert(parameterIndex == lastPathParameterToBind + 1,
					"We have moved the parameter index in a literal binding");
				Fx.Assert(segmentIndex < this.segments.Count,
					"Calculation of LastNonDefaultPathParameter,lastPathParameter or parameterIndex failed");
			}
			// We're done; skip to the beggining of the query parameters
			parameterIndex = lastPathParameter + 1;
		} else if (this.segments.Count > 0 || this.wildcard != null) {
			for (int i = 0; i < this.segments.Count; i++) {
				this.segments[i].Bind(parameters, ref parameterIndex, pathString);
			}
			if (this.wildcard != null) {
				this.wildcard.Bind(parameters, ref parameterIndex, pathString);
			}
		}
		if (this.ignoreTrailingSlash && (pathString[pathString.Length - 1] == '/')) {
			pathString.Remove(pathString.Length - 1, 1);
		}
		result.Path = pathString.ToString();
		// Binding the query :
		if ((this.queries.Count != 0) || (extraQueryParameters != null)) {
			StringBuilder query = new StringBuilder("");
			foreach (string key in this.queries.Keys) {
				this.queries[key].Bind(key, parameters, ref parameterIndex, query);
			}
			if (extraQueryParameters != null) {
				foreach (string key in extraQueryParameters.Keys) {
					if (this.queries.ContainsKey(key.ToUpperInvariant())) {
						// This can only be if the key passed has the same name as some literal key
						throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("parameters", SR.GetString(
							SR.UTBothLiteralAndNameValueCollectionKey, key));
					}
					string value = extraQueryParameters[key];
					string escapedValue = (string.IsNullOrEmpty(value) ? string.Empty : UrlUtility.UrlEncode(value, Encoding.UTF8));
					query.AppendFormat("&{0}={1}", UrlUtility.UrlEncode(key, Encoding.UTF8), escapedValue);
				}
			}
			if (query.Length != 0) {
				query.Remove(0, 1); // remove extra leading '&'
			}
			result.Query = query.ToString();
		}
		// Adding the fragment (if needed)
		if (this.fragment != null) {
			result.Fragment = this.fragment;
		}

		return result.Uri;
	}
	void BindTerminalDefaults(int numMatchedSegments, NameValueCollection boundParameters) {
		Fx.Assert(!this.HasWildcard, "There are no terminal default when ends with wildcard");
		Fx.Assert(numMatchedSegments < this.segments.Count, "Otherwise - no defaults to bind");
		Fx.Assert(this.variables != null, "Otherwise - no default values to bind");
		Fx.Assert(this.variables.DefaultValues != null, "Otherwise - no default values to bind");
		for (int i = numMatchedSegments; i < this.segments.Count; i++) {
			switch (this.segments[i].Nature) {
				case UriTemplatePartType.Variable: {
					UriTemplateVariablePathSegment vps = this.segments[i] as UriTemplateVariablePathSegment;
					Fx.Assert(vps != null, "How can that be? That its nature");
					this.variables.LookupDefault(vps.VarName, boundParameters);
				}
				break;

				default:
					Fx.Assert("We only support terminal defaults on Variable segments");
					break;
			}
		}
	}

	bool IsCandidatePathMatch(int numSegmentsInBaseAddress, string[] candidateSegments,
		out int numMatchedSegments, out Collection<string> relativeSegments) {
		int numRelativeSegments = candidateSegments.Length - numSegmentsInBaseAddress;
		Fx.Assert(numRelativeSegments >= 0, "bad segments num");
		relativeSegments = new Collection<string>();
		bool isStillMatch = true;
		int relativeSegmentsIndex = 0;
		while (isStillMatch && (relativeSegmentsIndex < numRelativeSegments)) {
			string segment = candidateSegments[relativeSegmentsIndex + numSegmentsInBaseAddress];
			// Mathcing to next regular segment in the template (if there is one); building the wire segment representation
			if (relativeSegmentsIndex < this.segments.Count) {
				bool ignoreSlash = (this.ignoreTrailingSlash && (relativeSegmentsIndex == numRelativeSegments - 1));
				UriTemplateLiteralPathSegment lps = UriTemplateLiteralPathSegment.CreateFromWireData(segment);
				if (!this.segments[relativeSegmentsIndex].IsMatch(lps, ignoreSlash)) {
					isStillMatch = false;
					break;
				}
				string relPathSeg = Uri.UnescapeDataString(segment);
				if (lps.EndsWithSlash) {
					Fx.Assert(relPathSeg.EndsWith("/", StringComparison.Ordinal), "problem with relative path segment");
					relPathSeg = relPathSeg.Substring(0, relPathSeg.Length - 1); // trim slash
				}
				relativeSegments.Add(relPathSeg);
			}
			// Checking if the template has a wild card ('*') or a final star var segment ("{*<var name>}"
			else if (this.HasWildcard) {
				break;
			} else {
				isStillMatch = false;
				break;
			}
			relativeSegmentsIndex++;
		}
		if (isStillMatch) {
			numMatchedSegments = relativeSegmentsIndex;
			// building the wire representation to segments that were matched to a wild card
			if (relativeSegmentsIndex < numRelativeSegments) {
				while (relativeSegmentsIndex < numRelativeSegments) {
					string relPathSeg = Uri.UnescapeDataString(candidateSegments[relativeSegmentsIndex + numSegmentsInBaseAddress]);
					if (relPathSeg.EndsWith("/", StringComparison.Ordinal)) {
						relPathSeg = relPathSeg.Substring(0, relPathSeg.Length - 1); // trim slash
					}
					relativeSegments.Add(relPathSeg);
					relativeSegmentsIndex++;
				}
			}
			// Checking if we matched all required segments already
			else if (numMatchedSegments < this.firstOptionalSegment) {
				isStillMatch = false;
			}
		} else {
			numMatchedSegments = 0;
		}

		return isStillMatch;
	}

	bool IsPathFullyEquivalent(UriTemplate other) {
		// Refer to the note on template equivalency at IsEquivalentTo
		// This method checks if both templates has a fully equivalent path.
		if (this.HasWildcard != other.HasWildcard) {
			return false;
		}
		if (this.segments.Count != other.segments.Count) {
			return false;
		}
		for (int i = 0; i < this.segments.Count; ++i) {
			if (!this.segments[i].IsEquivalentTo(other.segments[i],
				(i == this.segments.Count - 1) && !this.HasWildcard && (this.ignoreTrailingSlash || other.ignoreTrailingSlash))) {
				return false;
			}
		}
		return true;
	}

	BindInformation PrepareBindInformation(IDictionary<string, string> parameters, bool omitDefaults) {
		if (parameters == null) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("parameters");
		}

		IDictionary<string, string> extraParameters = new Dictionary<string, string>(UriTemplateHelpers.GetQueryKeyComparer());
		foreach (KeyValuePair<string, string> kvp in parameters) {
			if (string.IsNullOrEmpty(kvp.Key)) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("parameters",
					SR.GetString(SR.UTBindByNameCalledWithEmptyKey));
			}

			extraParameters.Add(kvp);
		}
		BindInformation bindInfo;
		ProcessDefaultsAndCreateBindInfo(omitDefaults, extraParameters, out bindInfo);
		return bindInfo;
	}
	BindInformation PrepareBindInformation(NameValueCollection parameters, bool omitDefaults) {
		if (parameters == null) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("parameters");
		}

		IDictionary<string, string> extraParameters = new Dictionary<string, string>(UriTemplateHelpers.GetQueryKeyComparer());
		foreach (string key in parameters.AllKeys) {
			if (string.IsNullOrEmpty(key)) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("parameters",
					SR.GetString(SR.UTBindByNameCalledWithEmptyKey));
			}

			extraParameters.Add(key, parameters[key]);
		}
		BindInformation bindInfo;
		ProcessDefaultsAndCreateBindInfo(omitDefaults, extraParameters, out bindInfo);
		return bindInfo;
	}
	void ProcessDefaultsAndCreateBindInfo(bool omitDefaults, IDictionary<string, string> extraParameters,
		out BindInformation bindInfo) {
		Fx.Assert(extraParameters != null, "We are expected to create it at the calling PrepareBindInformation");
		if (this.additionalDefaults != null) {
			if (omitDefaults) {
				foreach (KeyValuePair<string, string> kvp in this.additionalDefaults) {
					string extraParameter;
					if (extraParameters.TryGetValue(kvp.Key, out extraParameter)) {
						if (string.Compare(extraParameter, kvp.Value, StringComparison.Ordinal) == 0) {
							extraParameters.Remove(kvp.Key);
						}
					}
				}
			} else {
				foreach (KeyValuePair<string, string> kvp in this.additionalDefaults) {
					if (!extraParameters.ContainsKey(kvp.Key)) {
						extraParameters.Add(kvp.Key, kvp.Value);
					}
				}
			}
		}
		if (extraParameters.Count == 0) {
			extraParameters = null;
		}
		bindInfo = new BindInformation(extraParameters);
	}

	string UnescapeDefaultValue(string escapedValue) {
		if (string.IsNullOrEmpty(escapedValue)) {
			return escapedValue;
		}
		if (this.unescapedDefaults == null) {
			this.unescapedDefaults = new ConcurrentDictionary<string, string>(StringComparer.Ordinal);
		}

		return this.unescapedDefaults.GetOrAdd(escapedValue, Uri.UnescapeDataString);
	}

	struct BindInformation {
		IDictionary<string, string> additionalParameters;
		int lastNonDefaultPathParameter;
		int lastNonNullablePathParameter;
		string[] normalizedParameters;

		public BindInformation(string[] normalizedParameters, int lastNonDefaultPathParameter,
			int lastNonNullablePathParameter, IDictionary<string, string> additionalParameters) {
			this.normalizedParameters = normalizedParameters;
			this.lastNonDefaultPathParameter = lastNonDefaultPathParameter;
			this.lastNonNullablePathParameter = lastNonNullablePathParameter;
			this.additionalParameters = additionalParameters;
		}
		public BindInformation(IDictionary<string, string> additionalParameters) {
			this.normalizedParameters = null;
			this.lastNonDefaultPathParameter = -1;
			this.lastNonNullablePathParameter = -1;
			this.additionalParameters = additionalParameters;
		}

		public IDictionary<string, string> AdditionalParameters {
			get {
				return this.additionalParameters;
			}
		}
		public int LastNonDefaultPathParameter {
			get {
				return this.lastNonDefaultPathParameter;
			}
		}
		public int LastNonNullablePathParameter {
			get {
				return this.lastNonNullablePathParameter;
			}
		}
		public string[] NormalizedParameters {
			get {
				return this.normalizedParameters;
			}
		}
	}

	class UriTemplateDefaults : IDictionary<string, string> {
		Dictionary<string, string> defaults;
		ReadOnlyCollection<string> keys;
		ReadOnlyCollection<string> values;

		public UriTemplateDefaults(UriTemplate template) {
			this.defaults = new Dictionary<string, string>(StringComparer.OrdinalIgnoreCase);
			if ((template.variables != null) && (template.variables.DefaultValues != null)) {
				foreach (KeyValuePair<string, string> kvp in template.variables.DefaultValues) {
					this.defaults.Add(kvp.Key, kvp.Value);
				}
			}
			if (template.additionalDefaults != null) {
				foreach (KeyValuePair<string, string> kvp in template.additionalDefaults) {
					this.defaults.Add(kvp.Key.ToUpperInvariant(), kvp.Value);
				}
			}
			this.keys = new ReadOnlyCollection<string>(new List<string>(this.defaults.Keys));
			this.values = new ReadOnlyCollection<string>(new List<string>(this.defaults.Values));
		}

		// ICollection<KeyValuePair<string, string>> Members
		public int Count {
			get {
				return this.defaults.Count;
			}
		}
		public bool IsReadOnly {
			get {
				return true;
			}
		}

		// IDictionary<string, string> Members
		public ICollection<string> Keys {
			get {
				return this.keys;
			}
		}
		public ICollection<string> Values {
			get {
				return this.values;
			}
		}
		public string this[string key] {
			get {
				return this.defaults[key];
			}
			set {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new NotSupportedException(
					SR.GetString(SR.UTDefaultValuesAreImmutable)));
			}
		}

		public void Add(string key, string value) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new NotSupportedException(
				SR.GetString(SR.UTDefaultValuesAreImmutable)));
		}

		public void Add(KeyValuePair<string, string> item) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new NotSupportedException(
				SR.GetString(SR.UTDefaultValuesAreImmutable)));
		}
		public void Clear() {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new NotSupportedException(
				SR.GetString(SR.UTDefaultValuesAreImmutable)));
		}
		public bool Contains(KeyValuePair<string, string> item) {
			return (this.defaults as ICollection<KeyValuePair<string, string>>).Contains(item);
		}
		public bool ContainsKey(string key) {
			return this.defaults.ContainsKey(key);
		}
		public void CopyTo(KeyValuePair<string, string>[] array, int arrayIndex) {
			(this.defaults as ICollection<KeyValuePair<string, string>>).CopyTo(array, arrayIndex);
		}

		// IEnumerable<KeyValuePair<string, string>> Members
		public IEnumerator<KeyValuePair<string, string>> GetEnumerator() {
			return this.defaults.GetEnumerator();
		}
		public bool Remove(string key) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new NotSupportedException(
				SR.GetString(SR.UTDefaultValuesAreImmutable)));
		}
		public bool Remove(KeyValuePair<string, string> item) {
			throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new NotSupportedException(
				SR.GetString(SR.UTDefaultValuesAreImmutable)));
		}

		// IEnumerable Members
		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
			return this.defaults.GetEnumerator();
		}
		public bool TryGetValue(string key, out string value) {
			return this.defaults.TryGetValue(key, out value);
		}
	}

	class VariablesCollection {
		readonly UriTemplate owner;
		static ReadOnlyCollection<string> emptyStringCollection = null;
		Dictionary<string, string> defaultValues; // key is the variable name (in uppercase; as appear in the variable names lists)
		int firstNullablePathVariable;
		List<string> pathSegmentVariableNames; // ToUpperInvariant, in order they occur in the original template string
		ReadOnlyCollection<string> pathSegmentVariableNamesSnapshot = null;
		List<UriTemplatePartType> pathSegmentVariableNature;
		List<string> queryValueVariableNames; // ToUpperInvariant, in order they occur in the original template string
		ReadOnlyCollection<string> queryValueVariableNamesSnapshot = null;

		public VariablesCollection(UriTemplate owner) {
			this.owner = owner;
			this.pathSegmentVariableNames = new List<string>();
			this.pathSegmentVariableNature = new List<UriTemplatePartType>();
			this.queryValueVariableNames = new List<string>();
			this.firstNullablePathVariable = -1;
		}

		public static ReadOnlyCollection<string> EmptyCollection {
			get {
				if (emptyStringCollection == null) {
					emptyStringCollection = new ReadOnlyCollection<string>(new List<string>());
				}
				return emptyStringCollection;
			}
		}

		public Dictionary<string, string> DefaultValues {
			get {
				return this.defaultValues;
			}
		}
		public ReadOnlyCollection<string> PathSegmentVariableNames {
			get {
				if (this.pathSegmentVariableNamesSnapshot == null) {
					Interlocked.CompareExchange<ReadOnlyCollection<string>>(ref this.pathSegmentVariableNamesSnapshot, new ReadOnlyCollection<string>(
						this.pathSegmentVariableNames), null);
				}
				return this.pathSegmentVariableNamesSnapshot;
			}
		}
		public ReadOnlyCollection<string> QueryValueVariableNames {
			get {
				if (this.queryValueVariableNamesSnapshot == null) {
					Interlocked.CompareExchange<ReadOnlyCollection<string>>(ref this.queryValueVariableNamesSnapshot, new ReadOnlyCollection<string>(
						this.queryValueVariableNames), null);
				}
				return this.queryValueVariableNamesSnapshot;
			}
		}

		public void AddDefaultValue(string varName, string value) {
			int varIndex = this.pathSegmentVariableNames.IndexOf(varName);
			Fx.Assert(varIndex != -1, "Adding default value is restricted to path variables");
			if ((this.owner.wildcard != null) && this.owner.wildcard.HasVariable &&
				(varIndex == this.pathSegmentVariableNames.Count - 1)) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
					SR.GetString(SR.UTStarVariableWithDefaultsFromAdditionalDefaults,
					this.owner.originalTemplate, varName)));
			}
			if (this.pathSegmentVariableNature[varIndex] != UriTemplatePartType.Variable) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
					SR.GetString(SR.UTDefaultValueToCompoundSegmentVarFromAdditionalDefaults,
					this.owner.originalTemplate, varName)));
			}
			if (string.IsNullOrEmpty(value) ||
				(string.Compare(value, UriTemplate.NullableDefault, StringComparison.OrdinalIgnoreCase) == 0)) {
				value = null;
			}
			if (this.defaultValues == null) {
				this.defaultValues = new Dictionary<string, string>();
			}
			this.defaultValues.Add(varName, value);
		}

		public string AddPathVariable(UriTemplatePartType sourceNature, string varDeclaration, out bool hasDefaultValue) {
			Fx.Assert(sourceNature != UriTemplatePartType.Literal, "Literal path segments can't be the source for path variables");
			string varName;
			string defaultValue;
			ParseVariableDeclaration(varDeclaration, out varName, out defaultValue);
			hasDefaultValue = (defaultValue != null);
			if (varName.IndexOf(UriTemplate.WildcardPath, StringComparison.Ordinal) != -1) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new FormatException(
					SR.GetString(SR.UTInvalidWildcardInVariableOrLiteral, this.owner.originalTemplate, UriTemplate.WildcardPath)));
			}
			string uppercaseVarName = varName.ToUpperInvariant();
			if (this.pathSegmentVariableNames.Contains(uppercaseVarName) ||
				this.queryValueVariableNames.Contains(uppercaseVarName)) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
					SR.GetString(SR.UTVarNamesMustBeUnique, this.owner.originalTemplate, varName)));
			}
			this.pathSegmentVariableNames.Add(uppercaseVarName);
			this.pathSegmentVariableNature.Add(sourceNature);
			if (hasDefaultValue) {
				if (defaultValue == string.Empty) {
					throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
						SR.GetString(SR.UTInvalidDefaultPathValue, this.owner.originalTemplate,
						varDeclaration, varName)));
				}
				if (string.Compare(defaultValue, UriTemplate.NullableDefault, StringComparison.OrdinalIgnoreCase) == 0) {
					defaultValue = null;
				}
				if (this.defaultValues == null) {
					this.defaultValues = new Dictionary<string, string>();
				}
				this.defaultValues.Add(uppercaseVarName, defaultValue);
			}
			return uppercaseVarName;
		}
		public string AddQueryVariable(string varDeclaration) {
			string varName;
			string defaultValue;
			ParseVariableDeclaration(varDeclaration, out varName, out defaultValue);
			if (varName.IndexOf(UriTemplate.WildcardPath, StringComparison.Ordinal) != -1) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new FormatException(
					SR.GetString(SR.UTInvalidWildcardInVariableOrLiteral, this.owner.originalTemplate, UriTemplate.WildcardPath)));
			}
			if (defaultValue != null) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
					SR.GetString(SR.UTDefaultValueToQueryVar, this.owner.originalTemplate,
					varDeclaration, varName)));
			}
			string uppercaseVarName = varName.ToUpperInvariant();
			if (this.pathSegmentVariableNames.Contains(uppercaseVarName) ||
				this.queryValueVariableNames.Contains(uppercaseVarName)) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
					SR.GetString(SR.UTVarNamesMustBeUnique, this.owner.originalTemplate, varName)));
			}
			this.queryValueVariableNames.Add(uppercaseVarName);
			return uppercaseVarName;
		}

		public void LookupDefault(string varName, NameValueCollection boundParameters) {
			Fx.Assert(this.defaultValues.ContainsKey(varName), "Otherwise, we don't have a value to bind");
			boundParameters.Add(varName, owner.UnescapeDefaultValue(this.defaultValues[varName]));
		}

		public BindInformation PrepareBindInformation(IDictionary<string, string> parameters, bool omitDefaults) {
			if (parameters == null) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("parameters");
			}

			string[] normalizedParameters = PrepareNormalizedParameters();
			IDictionary<string, string> extraParameters = null;
			foreach (string key in parameters.Keys) {
				ProcessBindParameter(key, parameters[key], normalizedParameters, ref extraParameters);
			}
			BindInformation bindInfo;
			ProcessDefaultsAndCreateBindInfo(omitDefaults, normalizedParameters, extraParameters, out bindInfo);
			return bindInfo;
		}
		public BindInformation PrepareBindInformation(NameValueCollection parameters, bool omitDefaults) {
			if (parameters == null) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("parameters");
			}

			string[] normalizedParameters = PrepareNormalizedParameters();
			IDictionary<string, string> extraParameters = null;
			foreach (string key in parameters.AllKeys) {
				ProcessBindParameter(key, parameters[key], normalizedParameters, ref extraParameters);
			}
			BindInformation bindInfo;
			ProcessDefaultsAndCreateBindInfo(omitDefaults, normalizedParameters, extraParameters, out bindInfo);
			return bindInfo;
		}
		public BindInformation PrepareBindInformation(params string[] parameters) {
			if (parameters == null) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("values");
			}
			if ((parameters.Length < this.pathSegmentVariableNames.Count) ||
				(parameters.Length > this.pathSegmentVariableNames.Count + this.queryValueVariableNames.Count)) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new FormatException(
					SR.GetString(SR.UTBindByPositionWrongCount, this.owner.originalTemplate,
					this.pathSegmentVariableNames.Count, this.queryValueVariableNames.Count,
					parameters.Length)));
			}

			string[] normalizedParameters;
			if (parameters.Length == this.pathSegmentVariableNames.Count + this.queryValueVariableNames.Count) {
				normalizedParameters = parameters;
			} else {
				normalizedParameters = new string[this.pathSegmentVariableNames.Count + this.queryValueVariableNames.Count];
				parameters.CopyTo(normalizedParameters, 0);
				for (int i = parameters.Length; i < normalizedParameters.Length; i++) {
					normalizedParameters[i] = null;
				}
			}
			int lastNonDefaultPathParameter;
			int lastNonNullablePathParameter;
			LoadDefaultsAndValidate(normalizedParameters, out lastNonDefaultPathParameter,
				out lastNonNullablePathParameter);
			return new BindInformation(normalizedParameters, lastNonDefaultPathParameter,
				lastNonNullablePathParameter, this.owner.additionalDefaults);
		}
		public void ValidateDefaults(out int firstOptionalSegment) {
			Fx.Assert(this.defaultValues != null, "We are checking this condition from the c'tor");
			Fx.Assert(this.pathSegmentVariableNames.Count > 0, "Otherwise, how can we have default values");
			// Finding the first valid nullable defaults
			for (int i = this.pathSegmentVariableNames.Count - 1; (i >= 0) && (this.firstNullablePathVariable == -1); i--) {
				string varName = this.pathSegmentVariableNames[i];
				string defaultValue;
				if (!this.defaultValues.TryGetValue(varName, out defaultValue)) {
					this.firstNullablePathVariable = i + 1;
				} else if (defaultValue != null) {
					this.firstNullablePathVariable = i + 1;
				}
			}
			if (this.firstNullablePathVariable == -1) {
				this.firstNullablePathVariable = 0;
			}
			// Making sure that there are no nullables to the left of the first valid nullable
			if (this.firstNullablePathVariable > 1) {
				for (int i = this.firstNullablePathVariable - 2; i >= 0; i--) {
					string varName = this.pathSegmentVariableNames[i];
					string defaultValue;
					if (this.defaultValues.TryGetValue(varName, out defaultValue)) {
						if (defaultValue == null) {
							throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
								SR.GetString(SR.UTNullableDefaultMustBeFollowedWithNullables, this.owner.originalTemplate,
								varName, this.pathSegmentVariableNames[i + 1])));
						}
					}
				}
			}
			// Making sure that there are no Literals\WildCards to the right
			// Based on the fact that only Variable Path Segments support default values,
			//  if firstNullablePathVariable=N and pathSegmentVariableNames.Count=M then
			//  the nature of the last M-N path segments should be StringNature.Variable; otherwise,
			//  there was a literal segment in between. Also, there shouldn't be a wildcard.
			if (this.firstNullablePathVariable < this.pathSegmentVariableNames.Count) {
				if (this.owner.HasWildcard) {
					throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
						SR.GetString(SR.UTNullableDefaultMustNotBeFollowedWithWildcard,
						this.owner.originalTemplate, this.pathSegmentVariableNames[this.firstNullablePathVariable])));
				}
				for (int i = this.pathSegmentVariableNames.Count - 1; i >= this.firstNullablePathVariable; i--) {
					int segmentIndex = this.owner.segments.Count - (this.pathSegmentVariableNames.Count - i);
					if (this.owner.segments[segmentIndex].Nature != UriTemplatePartType.Variable) {
						throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
							SR.GetString(SR.UTNullableDefaultMustNotBeFollowedWithLiteral,
							this.owner.originalTemplate, this.pathSegmentVariableNames[this.firstNullablePathVariable],
							this.owner.segments[segmentIndex].OriginalSegment)));
					}
				}
			}
			// Now that we have the firstNullablePathVariable set, lets calculate the firstOptionalSegment.
			//  We already knows that the last M-N path segments (when M=pathSegmentVariableNames.Count and
			//  N=firstNullablePathVariable) are optional (see the previos comment). We will start there and
			//  move to the left, stopping at the first segment, which is not a variable or is a variable
			//  and doesn't have a default value.
			int numNullablePathVariables = (this.pathSegmentVariableNames.Count - this.firstNullablePathVariable);
			firstOptionalSegment = this.owner.segments.Count - numNullablePathVariables;
			if (!this.owner.HasWildcard) {
				while (firstOptionalSegment > 0) {
					UriTemplatePathSegment ps = this.owner.segments[firstOptionalSegment - 1];
					if (ps.Nature != UriTemplatePartType.Variable) {
						break;
					}
					UriTemplateVariablePathSegment vps = (ps as UriTemplateVariablePathSegment);
					Fx.Assert(vps != null, "Should be; that's his nature");
					if (!this.defaultValues.ContainsKey(vps.VarName)) {
						break;
					}
					firstOptionalSegment--;
				}
			}
		}

		void AddAdditionalDefaults(ref IDictionary<string, string> extraParameters) {
			if (extraParameters == null) {
				extraParameters = this.owner.additionalDefaults;
			} else {
				foreach (KeyValuePair<string, string> kvp in this.owner.additionalDefaults) {
					if (!extraParameters.ContainsKey(kvp.Key)) {
						extraParameters.Add(kvp.Key, kvp.Value);
					}
				}
			}
		}
		void LoadDefaultsAndValidate(string[] normalizedParameters, out int lastNonDefaultPathParameter,
			out int lastNonNullablePathParameter) {
			// First step - loading defaults
			for (int i = 0; i < this.pathSegmentVariableNames.Count; i++) {
				if (string.IsNullOrEmpty(normalizedParameters[i]) && (this.defaultValues != null)) {
					this.defaultValues.TryGetValue(this.pathSegmentVariableNames[i], out normalizedParameters[i]);
				}
			}
			// Second step - calculating bind constrains
			lastNonDefaultPathParameter = this.pathSegmentVariableNames.Count - 1;
			if ((this.defaultValues != null) &&
				(this.owner.segments[this.owner.segments.Count - 1].Nature != UriTemplatePartType.Literal)) {
				bool foundNonDefaultPathParameter = false;
				while (!foundNonDefaultPathParameter && (lastNonDefaultPathParameter >= 0)) {
					string defaultValue;
					if (this.defaultValues.TryGetValue(this.pathSegmentVariableNames[lastNonDefaultPathParameter],
						out defaultValue)) {
						if (string.Compare(normalizedParameters[lastNonDefaultPathParameter],
							defaultValue, StringComparison.Ordinal) != 0) {
							foundNonDefaultPathParameter = true;
						} else {
							lastNonDefaultPathParameter--;
						}
					} else {
						foundNonDefaultPathParameter = true;
					}
				}
			}
			if (this.firstNullablePathVariable > lastNonDefaultPathParameter) {
				lastNonNullablePathParameter = this.firstNullablePathVariable - 1;
			} else {
				lastNonNullablePathParameter = lastNonDefaultPathParameter;
			}
			// Third step - validate
			for (int i = 0; i <= lastNonNullablePathParameter; i++) {
				// Skip validation for terminating star variable segment :
				if (this.owner.HasWildcard && this.owner.wildcard.HasVariable &&
					(i == this.pathSegmentVariableNames.Count - 1)) {
					continue;
				}
				// Validate
				if (string.IsNullOrEmpty(normalizedParameters[i])) {
					throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("parameters",
						SR.GetString(SR.BindUriTemplateToNullOrEmptyPathParam, this.pathSegmentVariableNames[i]));
				}
			}
		}
		void ParseVariableDeclaration(string varDeclaration, out string varName, out string defaultValue) {
			if ((varDeclaration.IndexOf('{') != -1) || (varDeclaration.IndexOf('}') != -1)) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new FormatException(
					SR.GetString(SR.UTInvalidVarDeclaration, this.owner.originalTemplate, varDeclaration)));
			}
			int equalSignIndex = varDeclaration.IndexOf('=');
			switch (equalSignIndex) {
				case -1:
					varName = varDeclaration;
					defaultValue = null;
					break;

				case 0:
					throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new FormatException(
						SR.GetString(SR.UTInvalidVarDeclaration, this.owner.originalTemplate, varDeclaration)));

				default:
					varName = varDeclaration.Substring(0, equalSignIndex);
					defaultValue = varDeclaration.Substring(equalSignIndex + 1);
					if (defaultValue.IndexOf('=') != -1) {
						throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new FormatException(
							SR.GetString(SR.UTInvalidVarDeclaration, this.owner.originalTemplate, varDeclaration)));
					}
					break;
			}
		}
		string[] PrepareNormalizedParameters() {
			string[] normalizedParameters = new string[this.pathSegmentVariableNames.Count + this.queryValueVariableNames.Count];
			for (int i = 0; i < normalizedParameters.Length; i++) {
				normalizedParameters[i] = null;
			}
			return normalizedParameters;
		}
		void ProcessBindParameter(string name, string value, string[] normalizedParameters,
			ref IDictionary<string, string> extraParameters) {
			if (string.IsNullOrEmpty(name)) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("parameters",
					SR.GetString(SR.UTBindByNameCalledWithEmptyKey));
			}

			string uppercaseVarName = name.ToUpperInvariant();
			int pathVarIndex = this.pathSegmentVariableNames.IndexOf(uppercaseVarName);
			if (pathVarIndex != -1) {
				normalizedParameters[pathVarIndex] = (string.IsNullOrEmpty(value) ? string.Empty : value);
				return;
			}
			int queryVarIndex = this.queryValueVariableNames.IndexOf(uppercaseVarName);
			if (queryVarIndex != -1) {
				normalizedParameters[this.pathSegmentVariableNames.Count + queryVarIndex] = (string.IsNullOrEmpty(value) ? string.Empty : value);
				return;
			}
			if (extraParameters == null) {
				extraParameters = new Dictionary<string, string>(UriTemplateHelpers.GetQueryKeyComparer());
			}
			extraParameters.Add(name, value);
		}
		void ProcessDefaultsAndCreateBindInfo(bool omitDefaults, string[] normalizedParameters,
			IDictionary<string, string> extraParameters, out BindInformation bindInfo) {
			int lastNonDefaultPathParameter;
			int lastNonNullablePathParameter;
			LoadDefaultsAndValidate(normalizedParameters, out lastNonDefaultPathParameter,
				out lastNonNullablePathParameter);
			if (this.owner.additionalDefaults != null) {
				if (omitDefaults) {
					RemoveAdditionalDefaults(ref extraParameters);
				} else {
					AddAdditionalDefaults(ref extraParameters);
				}
			}
			bindInfo = new BindInformation(normalizedParameters, lastNonDefaultPathParameter,
				lastNonNullablePathParameter, extraParameters);
		}
		void RemoveAdditionalDefaults(ref IDictionary<string, string> extraParameters) {
			if (extraParameters == null) {
				return;
			}

			foreach (KeyValuePair<string, string> kvp in this.owner.additionalDefaults) {
				string extraParameter;
				if (extraParameters.TryGetValue(kvp.Key, out extraParameter)) {
					if (string.Compare(extraParameter, kvp.Value, StringComparison.Ordinal) == 0) {
						extraParameters.Remove(kvp.Key);
					}
				}
			}
			if (extraParameters.Count == 0) {
				extraParameters = null;
			}
		}
	}

	class WildcardInfo {
		readonly UriTemplate owner;
		readonly string varName;

		public WildcardInfo(UriTemplate owner) {
			this.varName = null;
			this.owner = owner;
		}
		public WildcardInfo(UriTemplate owner, string segment) {
			Fx.Assert(!segment.EndsWith("/", StringComparison.Ordinal), "We are expecting to check this earlier");

			bool hasDefault;
			this.varName = owner.AddPathVariable(UriTemplatePartType.Variable,
				segment.Substring(1 + WildcardPath.Length, segment.Length - 2 - WildcardPath.Length),
				out hasDefault);
			// Since this is a terminating star segment there shouldn't be a default
			if (hasDefault) {
				throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
					SR.GetString(SR.UTStarVariableWithDefaults, owner.originalTemplate,
					segment, this.varName)));
			}
			this.owner = owner;
		}

		internal bool HasVariable {
			get {
				return (!string.IsNullOrEmpty(this.varName));
			}
		}

		public void Bind(string[] values, ref int valueIndex, StringBuilder path) {
			if (HasVariable) {
				Fx.Assert(valueIndex < values.Length, "Not enough values to bind");
				if (string.IsNullOrEmpty(values[valueIndex])) {
					valueIndex++;
				} else {
					path.Append(values[valueIndex++]);
				}
			}
		}
		public void Lookup(int numMatchedSegments, Collection<string> relativePathSegments,
			NameValueCollection boundParameters) {
			Fx.Assert(numMatchedSegments == this.owner.segments.Count, "We should have matched the other segments");
			if (HasVariable) {
				StringBuilder remainingPath = new StringBuilder();
				for (int i = numMatchedSegments; i < relativePathSegments.Count; i++) {
					if (i < relativePathSegments.Count - 1) {
						remainingPath.AppendFormat("{0}/", relativePathSegments[i]);
					} else {
						remainingPath.Append(relativePathSegments[i]);
					}
				}
				boundParameters.Add(this.varName, remainingPath.ToString());
			}
		}
	}
}
